#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
using namespace std;

class WeightedGraph_quan {
private:
    int numVertices;
    vector<vector<int>> adjacencyMatrix;//二维的带权无相图
public:
    WeightedGraph_quan(int numVertices) : numVertices(numVertices) {
        adjacencyMatrix.resize(numVertices, vector<int>(numVertices, 0));//有几个顶点的话，就开n*n的空间，并且初始化为0
    }
    void addEdge(int src, int dest, int weight) {
        adjacencyMatrix[src][dest] = weight;//在图上标出两个点之间的权重
        adjacencyMatrix[dest][src] = weight;//邻接矩阵需要对称过去,如果是有向图，将这一行注释掉
    }
    void printGraph() {//打印输出邻接矩阵
        cout<<"    ";
        for(int i=0;i<numVertices;i++){
            cout<<i<<" ";
        }
        cout<<endl<<endl;
        int i=0;
        for (const auto &row: adjacencyMatrix) {
            cout<<i<<"   ";
            for (int val: row) {
                cout << val << " ";
            }
            cout << endl;
            i++;
        }
    }
    vector<vector<int>> Graph_get(){
        return adjacencyMatrix;
    }
    void primMST() {
        vector<int> parent(numVertices, -1);  // 记录顶点的父节点,记录该节点被那个节点连着
        vector<int> key(numVertices, INT_MAX);  // 记录顶点的权重，树到各个还没有收录到树中的点的距离
        vector<bool> inMST(numVertices, false);  // 记录顶点是否已包含在生成树中
        // 使用优先级队列存储边的权重和对应的顶点
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        // 起始顶点的权重设为0
        key[0] = 0;//初始默认自己只有自己相连接，所以权重设置为0
        pq.push(make_pair(0, 0));
        while (!pq.empty()) {
            int u = pq.top().second;  // 获取当前权重最小的顶点
            pq.pop();
            inMST[u] = true;
            // 更新与新加入顶点相邻的顶点的权重和父节点
            for (int v = 0; v < numVertices; ++v) {
                if (adjacencyMatrix[u][v] && !inMST[v] && adjacencyMatrix[u][v] < key[v]) {//遍历刚刚出队列元素所连接的边，并将那些边中，还没有拉入队列的边拉入队列,更新树到各个没有收录进来的每个点的距离
                    parent[v] = u;
                    key[v] = adjacencyMatrix[u][v];//这里的权重是该点v与它的父节点u的权重
                    pq.push(make_pair(key[v], v));  // 将更新后的顶点加入优先级队列
                }
//cout<<parent[v]<<" "<<key[v]<<" ";
            }
            //cout<<endl;
        }
        // 打印最小生成树
        int s=0;
        //cout << "Minimum Spanning Tree:" << endl;
        for (int v = 1; v < numVertices; ++v) {
            if(!inMST[v]){cout << -1 << endl;
                return;}
            //cout << parent[v] << " - " << v << " weight: " << adjacencyMatrix[parent[v]][v] << endl;
            s=s+adjacencyMatrix[parent[v]][v];
        }
        cout<<s;
    }
    void Dijkstra(int startNode, vector<int>& distances,vector<int>& parent) {
        distances.resize(numVertices, 99999);
        parent.resize(numVertices);
        for(int i=0;i<numVertices;i++){
            parent[i]=i;
        }
        distances[startNode] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push(make_pair(0, startNode));

        while (!pq.empty()) {
            int currentNode = pq.top().second;//每次取出离原点距离最小的，且还为被选中的点
            int currentDistance = pq.top().first;//到原点的距离
            pq.pop();
            if (currentDistance > distances[currentNode]) {//已经是最短路了
                continue;
            }
            for (int neighborNode = 0; neighborNode < numVertices; ++neighborNode) {
                int weight = adjacencyMatrix[currentNode][neighborNode];
                if (weight > 0) {//找到与这个节点连通的边
                    int newDistance = currentDistance + weight;//通过该节点的边的距离为，这个节点到原地的距离加上它到该点的距离
                    if (newDistance < distances[neighborNode]) {//如果从它到比从其他点到距离更近，更新距离
                        distances[neighborNode] = newDistance;
                        parent[neighborNode] = currentNode;
                        //cout<<distances[neighborNode]<<" ";
                        pq.push(make_pair(newDistance, neighborNode));//并将更新后的距离压入优先级队列
                    }
                }
            }

        }
    }
};
